package offer_test_60;

//长度为n的数组所有的数字都在0~n-1这个范围，超出任意重复的数字。
//例子{2,3,1,0,2,5,3}return 2or3
public class eleven_DuplicateNumber {
	public static void main(String[] args) {
		int[] array = { 2, 3, 1, 0, 2, 5, 3 };
		System.out.println(getDuplicateNum(array));
	}

	// 时间复杂度ON，空间复杂度O1的思路：
	// 长度为n的数组如果没有重复则数字n必定放在n处。否则就出现了重复。从数组头根据此规则进行数字的交换，第一次遇到重复则就是重复的数字
	public static int getDuplicateNum(int[] array) {
		int length = array.length;
		if (length == 0) {
			return -1;
		}
		for (int i = 0; i < length; i++) {
			while (array[i] != i) {
				int change = array[i];
				if (array[change] == array[i]) {
					return change;
				}
				int temp = array[change];
				array[change] = array[i];
				array[i] = temp;
			}
			if (array[i] == i) {
				continue;
			}

		}
		return -1;
	}
}
